#include "../tools.h"
using std::greater;
using std::less;

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> qMin;       // 大顶堆
    priority_queue<int, vector<int>, greater<int>> qMax;    // 小顶堆

    MedianFinder() {

    }
    
    void addNum(int num) {
        // 保证 qMax.size() == qMin.size() | qMin.size() + 1
        if(qMax.size() == 0 || num >= qMax.top()){   // 先插 qMax
            if(qMax.size() > qMin.size()){
                qMin.push(qMax.top());
                qMax.pop();
            }
            qMax.push(num);
        }
        else if(qMin.size() == 0 || num <= qMin.top()){                                       // 插 qMin
            if(qMin.size() == qMax.size()){
                qMax.push(qMin.top());
                qMin.pop();
            }
            qMin.push(num);
        }
        else{
            if(qMax.size() > qMin.size()) qMin.push(num);
            else qMax.push(num);
        }
    }
    
    double findMedian() {
        if(qMax.size() == qMin.size()) return (qMax.top() + qMin.top()) / 2.0;
        else return qMax.top();
    }
};

int main(int argc, char const *argv[])
{
    MedianFinder sol;

    sol.addNum(-1);
    sol.addNum(-2);
    cout << sol.findMedian() << endl;
    sol.addNum(-3);
    cout << sol.findMedian() << endl;
    sol.addNum(-4);
    sol.addNum(-5);
    cout << sol.findMedian() << endl;

    return 0;
}
